package com.yequan.leetcode.tree.maxDepth_104;

import com.yequan.leetcode.tree.TreeNode;

/**
 * //给定一个二叉树，找出其最大深度。
 * //
 * // 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 * //
 * // 说明: 叶子节点是指没有子节点的节点。
 * //
 * // 示例：
 * //给定二叉树 [3,9,20,null,null,15,7]，
 * //
 * //     3
 * //   / \
 * //  9  20
 * //    /  \
 * //   15   7
 * //
 * // 返回它的最大深度 3 。
 * // Related Topics 树 深度优先搜索
 *
 * @author : Administrator
 * @date : 2020/3/29
 */
public class MaxDepth {

    public int maxDepth(TreeNode root) {
        return helper(root);
    }

    /**
     * 1.遍历左子树深度
     * 2.遍历右子树深度
     * 3.取左右子树最大深度  加上根节点深度+1
     *
     * @param root
     * @return
     */
    private int helper(TreeNode root) {
        if (null == root) {
            return 0;
        } else {
            int leftDepth = helper(root.left);
            int rightDepth = helper(root.right);
            return Math.max(leftDepth, rightDepth) + 1;
        }
    }


}
